#define DEBUG
#include <cstdio>

using namespace std;

const int maxn=300000, maxk=19;

class Tree {
	public:
		int n, m, ind[maxn+1], to[2*maxn-1], link[2*maxn-1], size[maxn+1], dfn[maxn+1], bs[maxn+1][maxk+1], sbs[maxn+1], end[maxn+1], fa[maxn+1];

		void init(int n) {
			this->n = n, m=0;
			for (int i=1; i<=n; i++) {
				ind[i] = 0;
			}
		}

		void addSide(int u, int v) {
			m++;
			to[m] = v;
			link[m] = ind[u];
			ind[u] = m;
		}

		void initSize(int o, int f) {
			dfn[o] = ++dfn[0];
			fa[o] = f;
			size[o] = 1;
			bs[o][0] = sbs[o] = 0;
			for (int i=ind[o]; i; i=link[i]) {
				if (to[i]!=fa[o]) {
					initSize(to[i], o);
					size[o] += size[to[i]];
					if (size[bs[o][0]]<size[to[i]]) {
						sbs[o] = bs[o][0];
						bs[o][0] = to[i];
					} else if (size[sbs[o]]<size[to[i]]) {
						sbs[o] = to[i];
					}
				}
			}
			end[o] = dfn[0];
		}

		void build() {
			dfn[0] = 0;
			initSize(1, 0);
			for (int j=1; j<=maxk; j++) {
				for (int i=1; i<=n; i++) {
					bs[i][j] = bs[bs[i][j-1]][j-1];
				}
			}
		}

		int calcSize(int o, int t) {
			return dfn[o]<=dfn[t] && end[o]>=dfn[t] ? size[o]-size[t] : size[o];
		}

		int getCentroid(int o, int t) {
			int s = calcSize(o, t);
			for (int i=maxk; i>=0; i--) {
				if (bs[o][i] && 2*calcSize(bs[o][i], t)>=s && (dfn[bs[o][i]]<dfn[t] || dfn[bs[o][i]]>end[t])) {
					o = bs[o][i];
				}
			}
			if (sbs[o] && 2*calcSize(sbs[o], t)>=s) {
				o = sbs[o];
				for (int i=maxk; i>=0; i--) {
					if (bs[o][i] && 2*calcSize(bs[o][i], t)>=s && (dfn[bs[o][i]]<dfn[t] || dfn[bs[o][i]]>end[t])) {
						o = bs[o][i];
					}
				}
			}
			return 2*calcSize(o, t)==s ? o+fa[o] : o;
		}

		long long solve(int o) {
			long long ret=0;
			for (int i=ind[o]; i; i=link[i]) {
				if (to[i]!=fa[o]) {
					ret += getCentroid(1, to[i])+getCentroid(to[i], 0)+solve(to[i]);
				}
			}
			return ret;
		}
};

int main() {
	freopen("centroid.in", "r", stdin);
	freopen("centroid.out", "w", stdout);

	int t;
	scanf("%d", &t);
	for (; t>0; t--) {
		int n;
		scanf("%d", &n);
		static Tree tree;
		tree.init(n);
		for (int i=1; i<n; i++) {
			int u, v;
			scanf("%d %d", &u, &v);
			tree.addSide(u, v);
			tree.addSide(v, u);
		}
		tree.build();
		printf("%lld\n", tree.solve(1));
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}
